1. Field of the Invention
The present invention relates to a cryptographic identification process enabling a random support, called an identity module (e.g., a smart card, microprocessor, computer, etc.), to prove its identity to means implementing an application, or an interlocutor having verification means, using a protocol setting into action, without revealing the same, one or more secrets contained in the support.
Thus, an identification protocol is a dialogue, through a telecommunications network, between two entities, on the one hand a first entity wishing to prove its identity and which can, if appropriate, be equipped with a terminal (e.g., a computer having a smart card reader) and on the other hand a second entity able to dialogue with the first and perform certain verification calculations.
The first entity, whose identity is to be verified or checked, is hereinafter called the claimant and the second is called the verifier.
The present invention more particularly relates to a public key identification process, where the verifier has no need to know the secrets contained in the identity module of the claimant, but only non-confidential data (the public key) in order to carry out verification calculations.
2. Discussion of the Background
The RSA (initials of the authors RIVEST, SHAMIR, ADLEMAN) public key encryptation algorithm is described in U.S. Pat. No. 4,405,829. At present, it is the most widely used public key algorithm. It supplies signature diagrams also usable for identification purposes.
In the RSA algorithm, a choice is made of two separate prime numbers p and q and their product n is formed. A choice is also made of an integer e, which is prime with the smallest common multiple of (p-1) and (q-1) (or, if desired, which is prime with the product (p-1)(q-1).
In order to encrypt a message, previously placed in digital form u, u being between 0 and n-1, the eth power of u is calculated in the ring of modulo n integers, i.e. v=u.sup.e mod n. It is pointed out that the value of a modulo x integer integer n is equal to the remainder of the division of x by n.
For decrypting a message such as v, it is necessary to extract the eth root of the encrypted message v in the ring of the modulo n integers. This operation amounts to raising the number v to the power d, d being the inverse of the modulo e exponent, the smallest common multiple of the numbers (p-1) and (q-1). If the prime factors p and q are not known, the determination of d is impossible and, with it, the decrypting operation.
One of the first practical uses of the RSA process for identification purposes has been the following: an authority, responsible for the putting into place of an identification system, emits a RSA-type public key, i.e. in practice the two numbers n and e, said key being common to the complete system, and retains the corresponding secret elements (p and q). In each identity module of system users, said authority deposits the pair constituted by:
the identification number ID of the identity module; PA1 the eth rooth (or the inverse of the eth root), modulo n, of a number obtained from the number ID by applying to ID a redundancy function known by everyone (whereof an example can be found in ISO standard 9796), said eth root (or its inverse), calculated by the emission authority with the aid of secret elements held by it, is called "accreditation". PA1 reading the identity-accreditation pair contained in an identity module; PA1 calculating the eth power of the accreditation and ensuring that the result of this calculation and the application of the redundancy function to the identification number ID do indeed provide the same result. PA1 1. the party wishing to prove identity (the claimant) calculates the eth power modulo n of a random number r which he draws and deduces therefrom a number x, called the control and which he supplies to the verifier; PA1 2. the verifier draws at random a number b, called the question and sends it to the claimant; PA1 3. the claimant calculates e.g. the product of the random number r by the bth power of his accreditation, i.e. y=rS.sup.b mod n and sends the result y to the verifier, who can calculate the eth power of y and, as he knows the eth power of the accreditation S of the claimant, he is then able to verify consistency between x, b and y. PA1 a) two large prime numbers p and q define the integer n, the product of p by q, the number n being rendered public; PA1 b) the calculation support having to prove its identity contains a secret accreditation S between 1 and n-1, the modulo n accreditation cube, i.e. I=S.sup.3 mod n, being rendered public; PA1 c) the support of the claimant is provided with means able to draw at random an integer r between 1 and n-1 and calculate the cube of r modulo n, called the control x: x=r.sup.3 mod n; PA1 d) the claimant transmits the control x to the verifier; PA1 e) the verifier draws at random an integer b lower than the exponent 3, i.e. equal to 0, 1 or 2, said integer being called the question; PA1 f) the verifier transmits the question to the claimant; PA1 g) the claimant calculates the number y defined by: y=rS.sup.b mod n; PA1 h) the claimant transmits the number y to the verifier; PA1 i) the verifier raises to the cube the number y and calculates the product of the control x (which has been transmitted to him) by the power b of I (b drawn by him and I which is public), the verifier then comparing y.sup.3 and xI.sup.b mod n--if consistency arises, the claimant has correctly replied to the question and his authenticity is assumed.
The accreditations deposited in the identity modules can, initially, be used for passive identification purposes (i.e., requiring no calculation on the part of the party wishing to prove its identity). For the verifier, the protocol is then reduced to the following operations:
Such a passive identification demonstrates to the verifier that the party wishing to prove identity has data which can only have been emitted by the authority, which to a certain extent limits identity usurpations. However, nothing prevents a pirate able to intercept the claimant-verifier protocol or a dishonest verifier, from reusing for his own advantage the data supplied by the claimant.
Despite this fraud risk by reuse, the aforementioned passive identification is widely used in the banking field and in the field of telecommunications or phone cards. Supplementary precautions (black lists, etc.) to a certain extent limit the magnitude of frauds by reuse.
However, to solve the problem of fraud by the reuse of exchanged data and which is inherent in passive identification protocols, active identification protocols, i.e. requiring calculations on the part of the party wishing to prove identity, have been proposed. These protocols not only include the use of the RSA algorithm for signing a random question posed by the verifier, but also interactive diagrams where the claimant demonstrates to the verifier that he has one or more accreditations of the type defined hereinbefore and without revealing said accreditation or accreditations. The most widely used of such diagrams are the FIAT-SHAMIR and GUILLOU-QUISQUATER diagrams respectively shown in FIGS. 1 and 2. The FIAT-SHAMIR identification diagram is described in U.S. Pat. No. 4,748,668. The GUILLOU and QUISQUATER identification diagram is described in FR-A-2 620 248 (or its corresponding EP-A-311 470 or corresponding U.S. Pat. No. 5,218,637).
These two diagrams consist of one or more iterations of a base variant with three passes, in which:
These diagrams offer a double advantage for active identification. On the one hand, if it is possible to accept an insecurity level (defined as the maximum probability of success of a defrauder) of approximately 10.sup.-6, they are much less costly with respect to calculation time than a RSA signature. On the other hand, at least in their basic version are based on zero knowledge disclosure, so that exchanges linked with an identification procedure cannot assist a defrauder in seeking secret accreditations of a user.
Two configurations can be envisaged for implementation, namely on the claimant side, active identification diagrams demonstrating the possession of accreditations of the type described hereinbefore. In a first configuration, the identity module containing the accreditations has an adequate calculation power for performing all the calculations on this side. In a second configuration the identity module containing the accreditations does not perform the calculations itself, but instead allows them to take place in a terminal (e.g., a microcomputer able to read the accreditations in the identity module).
The second configuration, although slightly less reliable than the first, can still be useful for improving the security of the verification of identity modules initially designed for a passive identification. It is necessary to have confidence in the terminal used on the claimant side, but provided that said terminal is integrated, it is not possible for any fraud to come from the network or the verifier.
In the present invention, more particular interest is attached to the problem of use, according to the second configuration, of identity supports initially designed for a passive identification, in which a single accreditation corresponding to a public exponent e equal to 3 has been deposited. Most French bank cards, as well as other identity supports (e.g. telecommunications cards) are of this type.
The GUILLOU-QUISQUATER process is in theory usable by the terminal on the claimant side, for demonstrating to the verifier the possession of the accreditation. In this particular case, the GUILLOU-QUISQUATER process comprises the following operations:
The security of such a diagram is based on the very hypothesis of the RSA diagram. As both the integer n and the exponent 3 are public, it is difficult for a third party defrauder, to arrive at r by taking the cubic root of x, without knowing the factors p and q, whereof n is the product. Without the knowledge of r, the defrauder cannot correctly reply to the question posed by the verifier.
For such a process, as well as for other hitherto known identification diagrams, the situation where there is only a single accreditation corresponding to a public exponent equal to 3 leads to protocols which are very costly as regards communications. Thus, the security level of a basic exchange (control, question, answer) implementable under the aforementioned conditions is lower than or equal to 3 for the GUILLOU-QUISQUATER diagram. In order to arrive at an appropriate security level (insecurity below 2.sup.-16), it is consequently necessary to repeat the basic exchange at least a dozen times, which leads to an increase in the number of bits to be exchanged between the claimant and the verifier by a factor of at least ten.